// 单链表头文件

#include "stdio.h"
#include "malloc.h"

#define OK 1
#define ERROR 0

typedef int Status;
typedef int ElemType;

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;  //结点类型LNode，链表类型的定义LinkList

void CreateList(LinkList &L, int n) {
    LNode *p, *r;
    int i;
    L = (LinkList) malloc(sizeof(LNode));
    L->next = NULL;
    r = L;
    for (i = 0; i < n; i++) {
        p = (LinkList) malloc(sizeof(LNode));
        scanf("%d", &p->data);
        p->next = NULL;
        r->next = p;
        r = p;
    }
} //尾插法,正序创建链表,带头结点

int LocateElem(LinkList L, ElemType e) {
    if (L->next == NULL)
        return ERROR;
    LinkList p = L->next;
    int i = 1;
    while (p) {
        if (p->data == e)
            return i;
        p = p->next;
        i++;
    }
    return 0;
} //返回表中第一个与e相等的元素位序。若不存在，返回0

Status GetElem(LinkList L, int i, ElemType &e) {
    if (i < 1)
        return ERROR;
    if (L->next == NULL)
        return ERROR;
    LinkList p = L->next;
    int j = 1;
    for (j = 1; j < i && p; j++) {
        if (p->next == NULL)
            return ERROR;
        p = p->next;
    }
    if (i == j) {
        e = p->data;
        return OK;
    }
    return ERROR;
} //获取ai元素的值返回在e中。如果i不合法，返回ERROR，否则为e赋值，返回OK

Status ListDelete(LinkList &L, int i, ElemType &e) {
    LinkList p = L;
    int j = 0;
    while (p->
            next && j < i
                        - 1) {
        p = p->next;
        j++;
    }
    if (!(p->next) || j > i - 1)
        return ERROR;
    LinkList s = p->next;
    e = s->data;
    p->
            next = s->next;
    free(s);
    return OK;
} //实现在链表L上删除ai元素，并将该元素在e中返回。需要判断输入i的合法性。

Status ListInsert(LinkList &L, int i, ElemType e) {
    LinkList p = L;
    int j = 0;
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!p || j > i - 1)
        return ERROR;
    LinkList s = (LinkList) malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}//实现在链表中ai元素之前插入元素e,需要判断输入i的合法性。

int ListLength(LinkList L) {
    if (L->next == NULL)
        return 0;
    LinkList p = L->next;
    int i = 1;
    while (p) {
        i++;
        p = p->next;
    }
    return i - 1;
}//返回表的长度

void ListPrint(LinkList L) {
    if (L->next == NULL)
        return;
    LinkList p = L->next;
    int f = 0;
    while (p) {
        if (f == 0) {
            printf("%d", p->data);
            f = 1;
        }
        printf(" %d");
        p = p->next;
    }
} //打印输出表L中的各个元素